package com.leetcode.贪心;

/**
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置。
 * @author LZF
 *
 */
public class L45跳跃游戏II {
	public static void main(String[] args) {
		System.out.println(jump(new int[] {5,9,3,2,1,0,2,3,3,1,0,0}));
	}
	public static int jump(int[] nums) {
        if(nums.length == 1) return 0;
        int cnt = 1;//第一步
        int start = 1;//初始化第一步开始的下标
        int curDistance = nums[0];//初始化第cnt步所能到达的最远距离
        int nextDiatance = curDistance;//初始化第一步所能到达的最远距离
        while(start < nums.length){
        	//第cnt步能到达，就返回cnt
            if(nextDiatance >= nums.length - 1) break;
            for(int i = start;i <= curDistance;i++){
                nextDiatance = Math.max(nextDiatance,i + nums[i]);//不断累计cnt+1步所能到达的最远距离
                if(nextDiatance >= nums.length - 1) return cnt + 1;
            }
            cnt++;//如果第cnt步还没到达，则cnt就要加1，进入下一步的循环
            start = curDistance + 1;//下一步的开始
            curDistance = nextDiatance;//下一步所能到达的最远距离
        }
        return cnt;
    }
}
